Parcours dans un graphe (3) - Corrigé

Énoncé

Voici un graphe.

1. Peut-on parcourir une fois et une seule chacune de ses arêtes ?

2. Si cela est possible, peut-on partir de n'importe quel sommet ?

3. Proposer une chaîne eulérienne dans ce graphe.

Solution

1. Ce graphe comporte 4 sommets de degré 4 donc pair (les sommets 1, 2, 3, 4) et 2 sommets de degré 3 donc impair (les sommets 5 et 6). Donc, d'après le théorème d'Euler, il existe une chaîne eulérienne.

2. On doit partir (et arriver) sur un somment de degré impair.

3. Proposition de chaîne eulérienne : 5 - 3 - 1 - 4 - 3 - 2 - 6 - 1 - 2 - 4 - 5 - 6.